﻿#include <iostream>

#define MAX(a, b) (a>b?a:b)

/**
 * 暴力递归
 * 以index结尾的最长子数组长度
 */
static int recur(const int* numbers, const size_t numberCount, const int k, const int index)
{
    if (index == 0)
    {
        if (numbers[index] == k) return 1;
        return 0;
    }

    int sum = 0;
    int count = 0;
    for (int i = index; i >= 0; i--)
    {
        sum += numbers[i];
        if (sum == k)
        {
            count = index - i + 1;
            break;
        }
    }

    return MAX(recur(numbers, numberCount, k, index - 1), count);
}

static void byRecur(const int* numbers, const size_t numberCount, const int k)
{
    int longestSubLength = 0;
    int curSubLength;
    for (int i = 0; i < numberCount; i++)
    {
        curSubLength = recur(numbers, numberCount, k, i);
        longestSubLength = MAX(longestSubLength, curSubLength);
    }

    printf("longest sub length by recur: %d\n", longestSubLength);
}

/**
 * 滑动窗口
 */
static int bySlidingWindow(const int* numbers, const size_t numberCount, const int k)
{
    // 左闭右开
    int left = -1;
    int right = 0;
    int sum = 0;
    int maxSubLength = 0;
    int curLength = 0;
    while (right <= numberCount)
    {
        if (right - left == 1)
        {
            ++right;
            ++curLength;
            sum += numbers[right - 1];
            continue;
        }

        if (sum < k)
        {
            ++curLength;
            ++right;
            sum += numbers[right - 1];
            continue;
        }
		
        if (sum == k)
        {
            maxSubLength = MAX(maxSubLength, curLength);
            ++curLength;
            ++right;
            sum += numbers[right - 1];
            continue;
        }

        if (sum > k)
        {
            ++left;
            --curLength;
            sum -= numbers[left];
        }
    }

    printf("longest sub length by sliding window: %d\n", maxSubLength);
    return maxSubLength;
}

/**
 * 给定一个数组arr，该数组无序，但是每个值均为正数，再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组长度。
 * 例如，arr=[1,2,1,1,1], k=3
 * 累加和为3的最长子数组为[1,1,1], 所以结果返回3.
 * 要求：时间复杂度O(N), 额外空间复杂度O(1)
 * 
 * 思路：
 * 滑动窗体
 */
int main_sumOfTheLongestPositiveIntegerSubarrayEqualToK()
{
    int numbers[] = {2,1,1,1,1,1,1,3,3};
    int k = 5;
    int count = sizeof(numbers) / sizeof(int);

    byRecur(numbers, count, k);
    bySlidingWindow(numbers, count, k);

    return 0;
}